nondeterministic polynomial time complete problem

nondeterministic polynomial time complete problem
NP-полная задача, полиномиальная для недетерминированной машины Тьюринга задача (поиска и-принятия решения), решаемая за полиномиальное время на недетерминированной машине Тьюринга задача (поиска и-принятия решения)

English-Russian electronics dictionary .

Игры ⚽ Поможем написать реферат

Смотреть что такое "nondeterministic polynomial time complete problem" в других словарях:

  • NP-complete problem — ▪ computer science       any of a class of computational problems for which no efficient solution algorithm has been found. Many significant computer science problems belong to this class e.g., the traveling salesman problem, satisfiability… …   Universalium

  • P versus NP problem — Unsolved problems in computer science Is P = NP ? …   Wikipedia

  • P = NP problem — The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize… …   Wikipedia

  • NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… …   Wikipedia

  • Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… …   Wikipedia

  • NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Karp-Lipton theorem — The Karp–Lipton theorem in complexity theory states that if the boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :Pi 2 , = Sigma 2 , and therefore mathrm{PH} , = Sigma 2 ,.That… …   Wikipedia

  • Montgomery Blair High School — Motto Crescens Scientia (To Expand Knowledge) Established 1925 (opened 1935) Type Public (Magnet) Secondary …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»